#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: square.py 
@version:
@time: 2024/01/28

试着将题目抽象成一个从根节点0到叶子节点n的过程，逐层向下累加，
直到累加之和为n为止，此时的深度即为完全平方数的个数。

但是每一层累加时只能加上完全平方数，因此我们缩小了范围。

当给定的值为n时，只要1到int(n**0.5)的平方数是备选项。

例如，当n=13时，int(13**0.5)为3

             0.0
           /  |  \
        1,1  4,1 9,1
    /  |  \
2,2   5,2 10,2

对每个节点再继续执行相同操作，为了避免重复计算，将已经出现过的累加之和保存在一个集合中，
若此次累加得到的和已经出现过，则不记录该节点。

当累加之和已经得到n时，停止计算，返回深度值作为最终结果。如此一来，即将求完全平方数的题目转化为一棵树的广度优先搜索问题。
"""

from collections import deque


def square_bfs(n):
    selected = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
    visited = set()
    queue = deque([(0, 0)])
    while queue:
        current, height = queue.popleft()
        for i in selected:
            sum_ = current + i
            if sum_ == n:
                return height + 1
            if sum_ < n and sum_ not in visited:
                visited.add(sum_)
                queue.append((sum_, height + 1))


print(square_bfs(3))


def square_dynamic(n):
    dp = [i for i in range(n + 1)]
    for i in range(4, n + 1):
        for j in range(int(n ** .05), 0, -1):
            if i >= j ** 2:
                dp[i] = max(dp[i], dp[i - j ** j] + 1)
    return dp[n]


print(square_bfs(3))
